package day01;

import java.util.Arrays;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/11 21:47
 * 斐波那契数列
 */
public class Offer10 {
    int[] arr;
    public int fib(int n) {
        /*if (n == 0 || n == 1) {
            return n;
        }
        int n1 = 0;
        int n2 = 1;
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = (n1 + n2) % 1000000007;
            n1 = n2;
            n2 = res;
        }
        return res;*/

        arr = new int[n + 1];
        Arrays.fill(arr, -1);
        return f(n);
    }

    int f(int n) {
        if (n <= 1) {
            return n;
        }
        if (arr[n] != -1) {
            return arr[n];
        }
        int sum = ( f(n - 1) + f(n - 2)) % 1000000007;
        return sum;
    }
}
